<!DOCTYPE html>
<html lang="en">
    <head>
    <title>Rust - Subtyping and Variance - Tinusgraglin</title>
    
    
    <meta http-equiv="content-type" content="text/html; charset=utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1"><meta name="description" content="A Slice Rust - Subtyping and Variance How should we understand this?"/><meta name="keywords" content="rust, rust-language, rust-lifetime, rust-type-system" />
    <meta property="og:title" content="A Slice of Tgl -&nbsp;Rust - Subtyping and Variance" />
    <meta property="og:type" content="website"/><meta property="og:url" content="&#x2F;blog&#x2F;rust-subtyping&#x2F;"/><meta property="og:description" content="How should we understand this?"/>
    <link rel="preload" href="/blog/assets/fonts/FiraCode-Regular.woff2" as="font" type="font/woff2" crossorigin="anonymous">
    <link rel="preload" href="/blog/assets/fonts/FiraCode-Bold.woff2" as="font" type="font/woff2" crossorigin="anonymous">

    <link rel="stylesheet" href="/blog/style.css?h=97e262212a0704163528">
    <link rel="stylesheet" href=" /blog/color/orange.css?h=a5a5d7faf9d4bc3e0b18">
    
</head>
    <body>
        <div class="container center">
<header class="header">
    <div class="header__inner">
        <div class="header__logo">
            <a href="&#x2F;blog">
    <div class="logo">
        LIN
    </div>
</a>
        </div>
        <div class="menu-trigger">menu</div>
    </div>
    
    <nav class="menu">
        <ul class="menu__inner menu__inner--desktop">
            
            
                    <li>
                        <a href="
    
        /blog/about
    
">about</a>
                    </li>
                
            </ul>

        <ul class="menu__inner menu__inner--mobile">
            
        <li>
            <a href="
    
        /blog/about
    
">about</a>
        </li>
        </ul>
    </nav>

    </header>
<div class="content"><article class="post">
        <header>
            <h1 class="post-title">
                <a href="&#x2F;blog&#x2F;rust-subtyping&#x2F;">Rust - Subtyping and Variance</a>
            </h1>
            
    <div class="post-meta">
        <span class="post-date">2023.05.31
                [Updated: 2023.12.29]
                </span>

        <span class="post-author"></span>

        

    
    :: {<a href="/blog/categories/rust/">rust</a>} 

            
    ::
    #<a href="/blog/tags/rust-language/">rust-language</a>
        
    #<a href="/blog/tags/rust-lifetime/">rust-lifetime</a>
        
    #<a href="/blog/tags/rust-type-system/">rust-type-system</a>
        
    
            
        
    </div>

            
    


<div class="toc" id="nav-container">
	<p class="toc-head">Table of Contents</p>
		<div id="nav-content" >
		<ul>
		
			<li>
				<a href="/blog/rust-subtyping/#subtyping">Subtyping</a>
				
					<ul>
						
							<li>
								<a href="/blog/rust-subtyping/#case1-lifetime-related">Case1: Lifetime related</a>
							</li>
							
						
							<li>
								<a href="/blog/rust-subtyping/#case2-trait-related">Case2: Trait related</a>
							</li>
							
								<ul>
								
									<li>
										<a href="/blog/rust-subtyping/#super-trait-induced">Super-trait Induced</a>
										
									</li>
								
									<li>
										<a href="/blog/rust-subtyping/#higher-ranked-trait-bound-hrtb-induced">Higher-ranked Trait Bound (HRTB) Induced</a>
										
									</li>
								
								</ul>
							
						
							<li>
								<a href="/blog/rust-subtyping/#subtyping-property-of-parametric-generic-types-variance">Subtyping Property of Parametric Generic Types: Variance</a>
							</li>
							
						
					</ul>
				
			</li>
		
		</ul>
		</div>
</div>

</header><h1 id="subtyping">Subtyping<a class="zola-anchor" href="#subtyping" aria-label="Anchor link for: subtyping">§</a>
</h1>
<p>Subtyping is the situation where values of type <code>A</code> can be used as values of type <code>B</code>, type <code>A</code>
is then called a subtype of type <code>B</code>, or, conversely, type <code>A</code> is called a supertype of type <code>B</code>.
People often express this relationship as 'a value of type <code>A</code> is (also) a value of type <code>B</code>'.</p>
<p>This definition of subtyping directly gives one major use of it, another one is when
a value of type <code>B</code> is produced, it can be binded to a variable of any supertype of <code>B</code>.
In short, this type hierarchy gives us the ability to not just <em>be more specific</em>, but also
<em>be more general</em>.</p>
<p>Basic subtyping relationships can arise in the following cases:</p>
<h2 id="case1-lifetime-related">Case1: Lifetime related<a class="zola-anchor" href="#case1-lifetime-related" aria-label="Anchor link for: case1-lifetime-related">§</a>
</h2>
<p>A lifetime <code>'a</code> is a subtype of <code>'b</code> if the duration of <code>'a</code> covers that of <code>'b</code>, this is
written as <code>'a: 'b</code>.</p>
<h2 id="case2-trait-related">Case2: Trait related<a class="zola-anchor" href="#case2-trait-related" aria-label="Anchor link for: case2-trait-related">§</a>
</h2>
<h3 id="super-trait-induced">Super-trait Induced<a class="zola-anchor" href="#super-trait-induced" aria-label="Anchor link for: super-trait-induced">§</a>
</h3>
<p>A super-trait <code>SupTrait</code> of a trait <code>Trait</code> is a trait that a type must implement before it
can implement <code>Trait</code>, in other word, any type implement <code>SupTrait</code> is also a type implement
<code>Trait</code>, this is again written as <code>SupTrait: Trait</code>.</p>
<p>Now consider a type representing <em>some unknown type</em> that implements <code>SupTrait</code> (i.e. a <code>dyn SupTrait</code>),
since this unknown type must also implements <code>Trait</code>, it is also <em>some unknown type</em> that implements
<code>Trait</code> (i.e. a <code>dyn Trait</code>), thus <code>dyn SupTrait</code> is also a subtype of <code>dyn Trait</code>.</p>
<h3 id="higher-ranked-trait-bound-hrtb-induced">Higher-ranked Trait Bound (HRTB) Induced<a class="zola-anchor" href="#higher-ranked-trait-bound-hrtb-induced" aria-label="Anchor link for: higher-ranked-trait-bound-hrtb-induced">§</a>
</h3>
<p>Values of a type that implements <code>Trait&lt;T&gt;</code> for all <code>T</code> can, of course, be used as values of a type
that only implements <code>Trait&lt;Cat&gt;</code>, i.e. <code>dyn for&lt;T&gt; Trait&lt;T&gt;</code> is a subtype of <code>dyn Trait&lt;SomeT&gt;</code>.</p>
<h2 id="subtyping-property-of-parametric-generic-types-variance">Subtyping Property of Parametric Generic Types: Variance<a class="zola-anchor" href="#subtyping-property-of-parametric-generic-types-variance" aria-label="Anchor link for: subtyping-property-of-parametric-generic-types-variance">§</a>
</h2>
<blockquote>
<p>Variance is a property that type constructors have with respect to their arguments.</p>
</blockquote>
<p>A type constructor is any generic type with some arguments, e.g. <code>Vec&lt;T&gt;</code>, <code>&amp; 'lifetime T</code>,
<code>&amp;mut 'lifetime T</code>. Let's say <code>C&lt;T&gt;</code> is a type constructor with argument <code>T</code>, and type <code>Sub</code>
is a subtype of some type <code>Super</code>, then:</p>
<ul>
<li><code>C&lt;T&gt;</code> is covariant over <code>T</code> if <code>C&lt;Sub&gt;</code> is a subtype of <code>C&lt;Super&gt;</code></li>
<li><code>C&lt;T&gt;</code> is contravariant over <code>T</code> if <code>C&lt;Super&gt;</code> is a subtype of <code>C&lt;Sub&gt;</code></li>
<li><code>C&lt;T&gt;</code> is invariant over <code>T</code> if there is no subtyping relationship between <code>C&lt;Super&gt;</code> and
<code>C&lt;Sub&gt;</code>.</li>
</ul>
<hr />
<p>For example, in Rust, <code>&amp;'a T</code> is covariant over both <code>'a</code> and <code>T</code>, and <code>&amp;'a mut T</code> is covariant
over <code>'a</code>, <em>but</em> <strong>invariant</strong> over <code>T</code>. This is because, first, <em>contravariance</em> doesn't make
sense here; second, if it's covariant over <code>T</code>, then a function accepting a <code>&amp;mut Animal</code> and
turning the <code>Animal</code> to a <code>Dog</code> internally can turn a <code>Cat</code> into a <code>Dog</code> since <code>&amp;mut Cat</code> is
be a subtype of <code>&amp;mut Animal</code>!</p>
<p>Now looking back at <code>&amp;'a T</code>, it is covariant over <code>T</code>, is this safe given that Rust has all these
standard interior mutability wrappers (<code>Cell</code>, <code>RefCell</code>, ...)? That is, can we use a <code>&amp;'a RefCell&lt;Cat&gt;</code>
to turn the cat into a dog? Well, first, <code>&amp;'a RefCell&lt;Cat&gt;</code> is covariant over <code>RefCell&lt;Cat&gt;</code>, and,
the covariance chain has to stop here, <code>RefCell&lt;T&gt;</code> cannot be covariant over <code>T</code>. Indeed, the base
of all interior mutability wrapper types in Rust, the <code>UnsafeCell&lt;T&gt;</code>, is invariant over <code>T</code>, and
so does all these derived types, giving us the safety we want.</p>
<hr />
<p>The only contravariance case pops out when we consider the relationship between a function's type
and the types of its arguments. Say we need a <code>fn(Cat) -&gt; ...</code>, since this function expects a <code>Cat</code>,
any value of <code>Cat</code> type or any subtype can be used, so a <code>fn(BlackCat) -&gt; ...</code> won't satisfy our
need, but a <code>fn(Animal) -&gt; ...</code> is a valid option. On the other hand, a function that gives out a <code>Cat</code>
is surely a function that gives out a <code>Animial</code>, which is why <code>fn() -&gt; T</code> is covariant over <code>T</code>.</p>
<p>This is probably why in C# and Kotlin, you mark a generic type with <code>out</code> to indicates that the
outter class/type is covariant over that generic type, <code>in</code> to indicates the contravariant case.</p>
<hr />
<p>Here is a table summarizing variance properties of some basic types in Rust <a href="https://doc.rust-lang.org/reference/subtyping.html#variance">from the reference</a>:</p>
<table><thead><tr><th>Type</th><th>Variance in 'a</th><th>Variance in T</th></tr></thead><tbody>
<tr><td>&amp;'a T</td><td>covariant</td><td>covariant</td></tr>
<tr><td>&amp;'a mut T</td><td>covariant</td><td>invariant</td></tr>
<tr><td>*const T</td><td></td><td>covariant</td></tr>
<tr><td>*mut T</td><td></td><td>invariant</td></tr>
<tr><td>[T] and [T; n]</td><td></td><td>covariant</td></tr>
<tr><td>fn() -&gt; T</td><td></td><td>covariant</td></tr>
<tr><td>fn(T) -&gt; ()</td><td></td><td>contravariant</td></tr>
<tr><td>std::cell::UnsafeCell<T></td><td></td><td>invariant</td></tr>
<tr><td>std::marker::PhantomData<T></td><td></td><td>covariant</td></tr>
<tr><td>dyn Trait<T> + 'a</td><td>covariant</td><td>invariant</td></tr>
</tbody></table>
<p>Notice that, <code>&amp;'a T</code>, <code>&amp;'a mut T</code> and <code>dyn Trait + 'a</code> are all covariant over the lifetime <code>'a</code>, so whenever
a <code>&amp;'short T</code>, <code>&amp;'short mut T</code> or <code>dyn Trait + 'short</code> is needed, a <code>&amp;'long T</code>, <code>&amp;'long mut T</code> or <code>dyn Trait + 'long</code>
can be used:</p>
<pre data-lang="rust" style="background-color:#2b303b;color:#c0c5ce;" class="language-rust "><code class="language-rust" data-lang="rust"><span style="color:#b48ead;">struct </span><span>St&lt;</span><span style="color:#b48ead;">&#39;a</span><span>&gt;(&amp;</span><span style="color:#b48ead;">&#39;a str</span><span>)
</span><span>
</span><span style="color:#b48ead;">impl</span><span>&lt;</span><span style="color:#b48ead;">&#39;a</span><span>&gt; St&lt;</span><span style="color:#b48ead;">&#39;a</span><span>&gt; {
</span><span>    </span><span style="color:#b48ead;">fn </span><span style="color:#8fa1b3;">new</span><span>(</span><span style="color:#bf616a;">s</span><span>: &amp;</span><span style="color:#b48ead;">&#39;a str</span><span>) -&gt; </span><span style="color:#b48ead;">Self </span><span>{ St(s) }
</span><span>    </span><span style="color:#b48ead;">fn </span><span style="color:#8fa1b3;">replace</span><span>(&amp;</span><span style="color:#b48ead;">mut </span><span style="color:#bf616a;">self</span><span>, </span><span style="color:#bf616a;">s</span><span>: &amp;</span><span style="color:#b48ead;">&#39;a str</span><span>) { </span><span style="color:#bf616a;">self</span><span>.</span><span style="color:#d08770;">0 </span><span>= s }
</span><span>}
</span><span>
</span><span style="color:#b48ead;">static </span><span style="color:#d08770;">SECOND</span><span>: &amp;</span><span style="color:#b48ead;">&#39;static str </span><span>= &quot;</span><span style="color:#a3be8c;">Second</span><span>&quot;;
</span><span>
</span><span style="color:#b48ead;">fn </span><span style="color:#8fa1b3;">main</span><span>() {
</span><span>    </span><span style="color:#b48ead;">let</span><span> s = String::from(&quot;</span><span style="color:#a3be8c;">First</span><span>&quot;);
</span><span>    </span><span style="color:#b48ead;">let mut</span><span> st = St::new(&amp;s);
</span><span>    st.</span><span style="color:#96b5b4;">replace</span><span>(</span><span style="color:#d08770;">SECOND</span><span>); </span><span style="color:#65737e;">// Works!
</span><span>}
</span></code></pre>
<p>Or, whenever a <code>&amp;'long T</code>, <code>&amp;'long mut T</code> or <code>dyn Trait + 'long</code> is produced, they can be binded to a <code>&amp;'short T</code>,
<code>&amp;'short mut T</code> or <code>dyn Trait + 'short</code> variable, it is sometimes said that the compiler has automatically <strong>shorten</strong>
the lifetime in these cases.</p>
<hr />
<p>Notice also that, <code>dyn Trait&lt;T&gt;</code> is also invariant over <code>T</code>, the argument for this is similar to
what we have discussed: <code>&amp;dyn Trait&lt;T&gt;</code> is covariant over <code>dyn Trait&lt;T&gt;</code>, and <code>dyn Trait&lt;T&gt;</code> might
contain interior mutabilities, so it's possible that a <code>&amp;dyn Trait&lt;T&gt;</code> acts like a <code>&amp;mut T</code>, so
<code>dyn Trait&lt;T&gt;</code> can not be covariant over <code>T</code>, otherwise, you will be able to do the following:</p>
<pre data-lang="rust" style="background-color:#2b303b;color:#c0c5ce;" class="language-rust "><code class="language-rust" data-lang="rust"><span style="color:#b48ead;">trait </span><span>Trait&lt;T&gt; {
</span><span>    </span><span style="color:#b48ead;">fn </span><span style="color:#8fa1b3;">change_to</span><span>(&amp;</span><span style="color:#bf616a;">self</span><span>, </span><span style="color:#bf616a;">val</span><span>: T);
</span><span>}
</span><span>
</span><span style="color:#b48ead;">struct </span><span>CatHouse(Cell&lt;Cat&gt;)
</span><span>
</span><span style="color:#b48ead;">impl </span><span>Trait&lt;Cat&gt; </span><span style="color:#b48ead;">for </span><span>CatHouse {
</span><span>    </span><span style="color:#b48ead;">fn </span><span style="color:#8fa1b3;">change_to</span><span>(&amp;</span><span style="color:#bf616a;">self</span><span>, </span><span style="color:#bf616a;">val</span><span>: Cat) {
</span><span>        </span><span style="color:#65737e;">// In this impl, `T` in `Trait&lt;T&gt;` is simply `Cat`,
</span><span>        </span><span style="color:#65737e;">// how can anything go wrong?
</span><span>        </span><span style="color:#bf616a;">self</span><span>.</span><span style="color:#d08770;">0.</span><span style="color:#96b5b4;">set</span><span>(val)
</span><span>    }
</span><span>}
</span><span>
</span><span style="color:#b48ead;">let</span><span> cat_house = CatHouse(Cell::new(Cat::new()));
</span><span>
</span><span style="color:#65737e;">// if `dyn Trait&lt;T&gt;` is covariant over `T`, this is possible:
</span><span style="color:#b48ead;">let</span><span> r: &amp;dyn Trait&lt;Animal&gt; = &amp;cat_house;
</span><span>
</span><span style="color:#96b5b4;">to_dog</span><span>(r);
</span><span style="color:#65737e;">// !!! Now inside our cat house lives a dog!
</span><span>
</span><span style="color:#b48ead;">fn </span><span style="color:#8fa1b3;">to_dog</span><span>(</span><span style="color:#bf616a;">r</span><span>: &amp;dyn Trait&lt;Animal&gt;) {
</span><span>    </span><span style="color:#65737e;">// Here `T` in `Trait&lt;T&gt;` can be any animal!
</span><span>    </span><span style="color:#65737e;">// Since a `Dog` is a `Animal`, and the function is
</span><span>    </span><span style="color:#65737e;">// expecting a `Animal`, surely nothing can go wrong!
</span><span>    r.</span><span style="color:#96b5b4;">change_to</span><span>(Dog::new());
</span><span>}
</span><span>
</span><span style="color:#65737e;">// For a more real-world example, replace Cat, Animal and Dog with
</span><span style="color:#65737e;">// `&amp;&#39;outer_function_local T`, `&amp;&#39;static T` and `&amp;&#39;inner_function_local T`
</span></code></pre>
<hr />
<p>References:</p>
<ul>
<li>Rustnomicon - <a href="https://doc.rust-lang.org/nomicon/subtyping.html">Subtyping</a></li>
<li>Reference - <a href="https://doc.rust-lang.org/reference/subtyping.html">Subtyping</a></li>
<li><a href="https://www.youtube.com/watch?v=iVYWDIW71jk">Crust of Rust: Subtyping and Variance</a></li>
<li>RFC Book - <a href="https://rust-lang.github.io/rfcs/0387-higher-ranked-trait-bounds.html#subtyping-of-trait-references">HRTB</a></li>
</ul>


        
    

        
        
    </article></div>
    <div class="pagination">
        <div class="pagination__buttons">
            </div>
    </div>
<footer class="footer">
                    <div class="footer__inner"><div class="copyright">
            <span>© 2024 Tinusgraglin <span/>
            <span>:: Powered by <a href="https://www.getzola.org/">Zola</a>(<a href="https://www.rust-lang.org/">Rust</a>) and <a href="https://bun.sh">Bun</a>(<a href="https://ziglang.org">Zig</a>)</span>
        </div>
    <script type="text/javascript" src="/blog/assets/js/main.js"></script>
</div>
                    

                </footer></div>
    </body>
</html>
